SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Simplex tree</title>

</head>

Simplex tree

</h1>

</header>

In <a href="Topological_data_analysis" title="Topological data analysis">topological data analysis</a>, a simplex tree is a type of <a href="Trie" title="Trie">trie</a> used to represent efficiently any general <a href="Simplicial_complex" title="Simplicial complex">simplicial complex</a>. Through its nodes, this <a href="Data_structure" title="Data structure">data structure</a> notably explicitly represents all the simplices. Its flexible structure allows the implementation of many basic operations useful to computing <a href="Persistent_homology" title="Persistent homology">persistent homology</a>. This data structure was invented by Jean-Daniel Boissonnat and Clément Maria in 2014, in the article The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes.<a href="#cite_note-:0-1">[1]</a> This data structure offers efficient operations on sparse simplicial complexes. For dense or maximal simplices, Skeleton-Blocker<a href="#cite_note-2">[2]</a> representations or Toplex Map<a href="#cite_note-:1-3">[3]</a> representations are used.

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

Many researchers in topological data analysis consider the simplex tree to be the most compact simplex-based data structure for simplicial complexes, and a data structure allowing an intuitive understanding of simplicial complexes due to integrated usage of their mathematical properties.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-:1-3">[3]</a><a href="#cite_note-:2-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="Heuristic_definition">Heuristic definition</h3></div>

Consider any simplicial complex is a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> composed of <a href="Point_(geometry)" title="Point (geometry)">points</a> (0 dimensions), <a href="Line_segment" title="Line segment">line segments</a> (1 dimension), <a href="Triangle" title="Triangle">triangles</a> (2 dimensions), and their n-dimensional counterparts, called <a href="Simplex" title="Simplex">n-simplexes</a> within a topological space. By the mathematical properties of simplexes, any n-simplex is composed of multiple <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)}</annotation>

</semantics>

</math><img src="./df88c6333caaf6471cf277f24b802ff9931b133e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.207ex; height:2.843ex;" alt="{\displaystyle (n-1)}" loading="lazy">-simplexes. Thus, lines are composed of points, triangles of lines, and tetrahedrons of triangles. Notice each higher level adds 1 vertex to the vertices of the n-simplex. The data structure is simplex-based, therefore, it should represent all simplexes uniquely by the points defining the simplex. A simple way to achieve this is to define each simplex by its points in sorted order.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {K} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {K} }</annotation>

</semantics>

</math><img src="./715131ccf06a4d6af0074374757de835af3889e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \mathrm {K} }" loading="lazy"> be a simplicial complex of dimension k, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> its vertex set, where vertices are labeled from 1 to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert V\right\vert }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert V\right\vert }</annotation>

</semantics>

</math><img src="./0e225010d26df52e18ef55e3d92bab6d9bbe1b48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle \left\vert V\right\vert }" loading="lazy"> and ordered accordingly. Now, construct a dictionary size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert V\right\vert }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert V\right\vert }</annotation>

</semantics>

</math><img src="./0e225010d26df52e18ef55e3d92bab6d9bbe1b48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle \left\vert V\right\vert }" loading="lazy"> containing all vertex labels in order. This represents the 0-dimensional simplexes. Then, for the path to the initial dictionary of each entry in the initial dictionary, add as a child dictionary all vertices fully-connected to the current set of vertices, all of which have a label greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy">. Represent this step on k levels. Clearly, considering the first dictionary as depth 0, any entry at depth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> of any dictionary in this data structure uniquely represents a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy">-simplex within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {K} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {K} }</annotation>

</semantics>

</math><img src="./715131ccf06a4d6af0074374757de835af3889e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \mathrm {K} }" loading="lazy">. For completeness, the point to the initial dictionary is considered the representation of the empty simplex. For the practicality of the operations, labels that are repeated on the same level are linked together, forming a looped <a href="Linked_list" title="Linked list">linked list</a>. Finally, child dictionaries also have pointers to their parent dictionary, for fast ancestor access.<a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Constructive_definition">Constructive definition</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {K} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {K} }</annotation>

</semantics>

</math><img src="./715131ccf06a4d6af0074374757de835af3889e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \mathrm {K} }" loading="lazy"> be a simplicial complex of dimension k. We begin by decomposing the simplicial complex into mutually exclusive simplexes. This can be achieved in a greedy way by iteratively removing from the simplicial complex the highest order simplexes until the simplicial complex is empty. We then need to label each vertex from 1 to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\vert V\right\vert }">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\vert V\right\vert }</annotation>

</semantics>

</math><img src="./0e225010d26df52e18ef55e3d92bab6d9bbe1b48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle \left\vert V\right\vert }" loading="lazy"> and associate each simplex with its corresponding "word", that is the ordered list of its vertices by label. Ordering the labels ensures no repetition in the simplex tree, as there is only one way to describe a simplex. We start with a null root, representing the null simplex. Then, we iterate through all simplexes, and through each label of each simplex word. If the label is available as a child to the current root, make that child the temporary root of the insertion process, otherwise, create a new node for the child, make it the new temporary root, and continue with the rest of the word. During this process, k dictionaries are maintained with all the labels and insert the address of the node for the corresponding label. If an address is already at that space in the dictionary, a pointer is created from the old node to the new node. Once the process is finished, all children of each node are entered into a dictionary, and all pointers are looped to make looped linked lists. A wide range of dictionaries could be applied here, like hash tables, but some operations assume the possibility of an ordered traversal of the entries, leading most of the implementations to use red-black trees are dictionaries.<a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2></div>

While simplex trees are not the most space efficient data structures for simplicial <a href="Complex_representation" title="Complex representation">complex representation</a>, their operations on sparse data are considered state-of-art. Here, we give the bounds of different useful operations possible through this representation. Many implementations of these operations are available.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-:2-4">[4]</a><a href="#cite_note-:3-5">[5]</a><a href="#cite_note-6">[6]</a><a href="#cite_note-:4-7">[7]</a>

We first introduce the notation. Consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> is a given simplex, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> is a given node corresponding to the last vertex of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> is the label associate to that node, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> is the depth of that node, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is the dimension of the simplicial complex, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{\sigma }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{\sigma }}</annotation>

</semantics>

</math><img src="./68ac3c73d76525bb1e898c733b18410ab9ab6ac9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.097ex; height:2.509ex;" alt="{\displaystyle D_{\sigma }}" loading="lazy"> is the maximal number of operations to access <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> in a dictionary (if the dictionary is a red-black tree, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{\sigma }=O(log(deg(\sigma )))}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{\sigma }=O(log(deg(\sigma )))}</annotation>

</semantics>

</math><img src="./638b915a04967181c17578c0ae0eeac70c100094.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.078ex; height:2.843ex;" alt="{\displaystyle D_{\sigma }=O(log(deg(\sigma )))}" loading="lazy"> is the complexity) . Consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{s}}</annotation>

</semantics>

</math><img src="./3b6d160c0ac08478db6e852c204a78cd9bc2e14d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.665ex; height:2.509ex;" alt="{\displaystyle C_{s}}" loading="lazy"> is the number of cofaces of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{l}^{>j}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{l}^{>j}}</annotation>

</semantics>

</math><img src="./631f3e228776521f43d3c8289c16d6f906346a78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.311ex; height:3.509ex;" alt="{\displaystyle N_{l}^{>j}}" loading="lazy"> is the number of nodes of the simplex tree ending with the label <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> at depth greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">. Notice <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{l}^{>j}\leq C_{s}}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{l}^{>j}\leq C_{s}}</annotation>

</semantics>

</math><img src="./c04182538cd1890ff63f517ce62655a71984d54d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.075ex; height:3.509ex;" alt="{\displaystyle N_{l}^{>j}\leq C_{s}}" loading="lazy">.

<ol><li>Search, insert and remove words are done in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(jD_{\sigma })}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(jD_{\sigma })}</annotation>

</semantics>

</math><img src="./ff95624eaeea9f77d9d5c92f6871aac9a683aaf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.637ex; height:2.843ex;" alt="{\displaystyle O(jD_{\sigma })}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a></li>

<li>Insert and remove an entire simplex is done in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(2^{j}D_{\sigma })}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(2^{j}D_{\sigma })}</annotation>

</semantics>

</math><img src="./b815544eb4ecc7f64420c22981707234f831b241.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.752ex; height:3.176ex;" alt="{\displaystyle O(2^{j}D_{\sigma })}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a></li>

<li>Computing <a href="Persistent_homology" title="Persistent homology">persistent homology</a>, or in a more involved way, computing <a href="Betti_number" title="Betti number">Betti numbers</a>, using a simplex tree most efficiently remains an open problem, however, current algorithms for this task on sparse simplicial complexes achieve state-of-art performance.<a href="#cite_note-:2-4">[4]</a></li>

<li>The structure of simplex trees allows for elementary collapse of collapsible simplexes, however the bounds of this operation in the general case are unknown.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-:3-5">[5]</a><a href="#cite_note-:4-7">[7]</a></li>

<li>A subcase of elementary collapse is edge-contraction. <a href="Edge_contraction" title="Edge contraction">Edge contraction</a> can be</li></ol>

achieved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(kN_{l}^{>j}+C_{s}D_{\sigma })}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(kN_{l}^{>j}+C_{s}D_{\sigma })}</annotation>

</semantics>

</math><img src="./5fbd2f0abb7af900765fefa58f3530623ce0fdf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.707ex; height:3.509ex;" alt="{\displaystyle O(kN_{l}^{>j}+C_{s}D_{\sigma })}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a>

<ol><li>Locating cofaces of given simplex can be achieved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(kN_{l}^{>j})}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(kN_{l}^{>j})}</annotation>

</semantics>

</math><img src="./391b12a133cb36758780c5d8fe7a908384d672ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.105ex; height:3.509ex;" alt="{\displaystyle O(kN_{l}^{>j})}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a></li>

<li>Locating cofacets of given simplex can be achieved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(j^{2}D_{\sigma })}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(j^{2}D_{\sigma })}</annotation>

</semantics>

</math><img src="./e0e484a00e4e7bbb825017435ca5da638249de7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.692ex; height:3.176ex;" alt="{\displaystyle O(j^{2}D_{\sigma })}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a></li></ol>

As for construction, as seen in the constructive definition, construction is proportional to the number and complexity of simplexes in the simplicial complex. This can be especially expensive if the simplicial complex is dense. However, some optimizations for particular simplicial complexes, including for <a href="Flag_complex" class="mw-redirect" title="Flag complex">Flag complexes</a>, <a href="Vietoris%E2%80%93Rips_complex" title="Vietoris–Rips complex">Rips complexes</a> and Witness complexes.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Simplex trees are efficient in sparse simplicial complexes. For this purpose, many persistent homology algorithms focusing on high-dimensional real data (often sparse) use simplex trees within these algorithms. While simplex trees are not as efficient as incidence matrices, their simplex-based structure allows them to be useful and efficient for simplicial complex storage within persistent homology algorithms.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBoissonnatMaria2014" class="citation journal cs1">Boissonnat, Jean-Daniel; Maria, Clément (November 2014). "The Simplex Tree: an Efficient Data Structure for General Simplicial Complexes". Algorithmica. 70 (3): 406–427. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2001.02581">2001.02581</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-014-9887-3">10.1007/s00453-014-9887-3</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0178-4617">0178-4617</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15335393">15335393</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFSalinas2020" class="citation web cs1">Salinas, David (7 February 2020). <a rel="nofollow" class="external text" href="https://gudhi.inria.fr/doc/3.1.1/group__skbl.html">"Skeleton-Blocker"</a>. Geometry Understanding in Higher Dimensions. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-:1-3">^ <a href="#cite_ref-:1_3-0">a</a> <a href="#cite_ref-:1_3-1">b</a> <cite id="CITEREFGodi2020" class="citation web cs1">Godi, Francois (7 February 2020). <a rel="nofollow" class="external text" href="https://gudhi.inria.fr/doc/latest/group__toplex__map.html">"Toplex Map"</a>. Geometry Understanding in Higher Dimensions. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-:2-4">^ <a href="#cite_ref-:2_4-0">a</a> <a href="#cite_ref-:2_4-1">b</a> <a href="#cite_ref-:2_4-2">c</a> <cite id="CITEREFBoissonnat" class="citation web cs1">Boissonnat, Jean-Daniel. <a rel="nofollow" class="external text" href="https://gudhi.inria.fr/python/latest/simplex_tree_ref.html">"Simplex tree reference manual"</a>. Geometry Understanding in Higher Dimensions. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-:3-5">^ <a href="#cite_ref-:3_5-0">a</a> <a href="#cite_ref-:3_5-1">b</a> <cite id="CITEREFPiekenbrock2020" class="citation web cs1">Piekenbrock, Matt (13 September 2020). <a rel="nofollow" class="external text" href="https://rdrr.io/cran/simplextree/man/simplex_tree.html">"simplex_tree: Simplex Tree"</a>. rdrr.io. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFNanda" class="citation web cs1">Nanda, Vidit. <a rel="nofollow" class="external text" href="http://people.maths.ox.ac.uk/nanda/perseus/index.html">"Perseus, the Persistent Homology Software"</a>. The Perseus Software Project for Rapid Computation of Persistent Homology. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-:4-7">^ <a href="#cite_ref-:4_7-0">a</a> <a href="#cite_ref-:4_7-1">b</a> <cite id="CITEREFMorozov2019" class="citation web cs1">Morozov, Dmitriy (2019). <a rel="nofollow" class="external text" href="https://mrzv.org/software/dionysus2/tutorial/basics.html">"Basics"</a>. Dionysus 2. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFMorozov2019" class="citation web cs1">Morozov, Dmitriy (2019). <a rel="nofollow" class="external text" href="https://mrzv.org/software/dionysus2/tutorial/rips.html">"Vietoris–Rips Complexes"</a>. Dionysus 2. Retrieved 9 December 2021.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFMandal2020" class="citation journal cs1 cs1-prop-long-vol">Mandal, Sayan (2020). <a rel="nofollow" class="external text" href="https://gradsch.osu.edu/calendar/events/applications-persistent-homology-and-cycle">"Applications of Persistent Homology and Cycles"</a>. The Ohio State University. PHD Thesis.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-10" href="https://en.wikipedia.org/wiki/?title=Simplex_tree&oldid=1275053119">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>